class Sea(object):
    def hasShips(self, topRight, bottomLeft):
        """
        :type topRight: Point
          :type bottomLeft: Point
        :rtype bool
        """
        return True


class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y


class Solution(object):
    def countShips(self, sea, topRight, bottomLeft):
        """
        :type sea: Sea
        :type topRight: Point
        :type bottomLeft: Point
        :rtype: integer
        """
        def search(top, bottom):
            if bottom.x == top.x and bottom.y == top.y:
                if sea.hasShips(top, bottom):
                    return 1
                else:
                    return 0
            else:
                if not sea.hasShips(top, bottom):
                    return 0
                else:
                    if bottom.x == top.x:
                        left_top = Point(bottom.x, (bottom.y + top.y) // 2)
                        right_bottom = Point(bottom.x, (bottom.y + top.y) // 2 + 1)
                        return search(left_top, bottom) + search(top, right_bottom)
                    else:
                        if bottom.y == top.y:
                            left_top = Point((bottom.x + top.x) // 2, top.y)
                            right_bottom = Point((bottom.x + top.x) // 2 + 1, top.y)
                            return search(left_top, bottom) + search(top, right_bottom)
                        else:
                            mid_x = (bottom.x + top.x) // 2
                            mid_y = (bottom.y + top.y) // 2
                            count1 = search(Point(mid_x, mid_y), bottom)
                            count2 = search(Point(mid_x, top.y), Point(bottom.x, mid_y + 1))
                            count3 = search(top, Point(mid_x + 1, mid_y + 1))
                            count4 = search(Point(top.x, mid_y), Point(mid_x + 1, bottom.y))
                            return count1 + count2 + count3 + count4
        return search(topRight, bottomLeft)


